package com.atguigu.dp;

//使用动态规划解决最大子数组和问题
public class P53 {
    public static void main(String[] args) {
        //期望输出：6
        int[] arr =  {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(arr));
    }

    private static int max = Integer.MIN_VALUE ;
    private static int max1 ;
    private static int maxSubArray(int[] arr) {
        max1 = arr[0];
        if(arr.length==1){
            return arr[0];
        }

        for(int i = 1 ; i<arr.length ; i++){
            max1 = Math.max(arr[i],arr[i]+max1);
            max = Math.max(max , max1);
        }
        return max ;
    }
}
